1. Field of the Invention
The present invention relates to the field of program code compilation and more particularly to matching intermediate language patterns during code compilation.
2. Description of the Related Art
Program code compilation refers to the transformation of a computer program embodied by source code into machine instructions executable by a central processor unit (CPU) in a computing system. Generally, during program code compilation, the compiler parses the source code for the computer program in order to generate an intermediate representation for the computer program. In particular, the intermediate representation can provide a stack-based representation of the programmatic expressions of the computer program.
The intermediate representation of the code in turn can be transformed into machine executable instructions. The transformation of the intermediate representation of the code into machine executable instructions ordinarily involves the pattern matching of intermediate language expressions and the emission of templated instructions specific to the target platform. Pattern Matchers can also be used in compiler optimization transformations that rely on recognizing idioms (that is, commonly used programmatic practices and algorithms) in the program being compiled. In these cases, the transformations promoted by the pattern matchers would modify the intermediate representation (rather than generate code directly), as other optimization transformation of the intermediate representation may be enabled as a result. Pattern matchers can be written manually to suit a specific target platform, or pattern matchers can be generalized to accommodate multiple different target platforms.
Pattern matchers can also be written manually to match a specific programming idiom in the input, or generalized to match multiple variations of the programming idiom. As an example, United States Patent Application Publication Nos. 2006/0206876 and 2006/0048122 by Christopher Barton et al. and United States Patent Application Publication No. 2007/0088697 by Charlebois et al. each disclose an expression matching and transformation programming framework (EMTF) for pattern matching of intermediate representation and for transforming intermediate language expression trees, such that pattern matching can be embedded within a source program.
The use of an EMTF to define a pattern matcher provides inherent advantages including the ease of embedding the pattern matchers within compiler code and the similarity of the EMTF syntax to the abstract representation of intermediate representation expressions. Still, the use of EMTF requires a significant learning curve and EMTF can be somewhat confusing for the developer when designing patterns for matching without the requisite experience in pattern matching. In addition, it can be time-consuming to correctly design pattern matchers for very large input patterns. Pattern matchers in general can be too precise and often fail to catch input patterns that observe the same desired behavior using slightly different code, for example different symbols, constants, labels, and the like. In particular, it is well known that symbol identifiers used in intermediate language representation often can be assigned to symbols that vary depending upon the compiled source file. Additionally, pattern matchers generally are designed to capture a specific set of patterns. Where other inputs that observe the desired behavior can be found, additional pattern matchers must be added to disambiguate the found inputs. Alternatively, existing pattern matchers must be extended to recognize the additional inputs observing the desired behavior. Finally, changes in the behavior of a compiler inherent to the development cycle of the compiler can result in even the most flexible pattern matchers failing to match or incorrectly matching an input if the input to the pattern matcher changes due to an implementation change or a new optimization added to the compiler. Consequently, pattern matchers typically are avoided in optimizers for optimizing compiled code.